|
In mathematics, Property B is a certain set theoretic property. Formally, given a finite set ''X'', a collection ''C'' of subsets of ''X'', all of size ''n'', has Property B if we can partition ''X'' into two disjoint subsets ''Y'' and ''Z'' such that every set in ''C'' meets both ''Y'' and ''Z''. The smallest number of sets in a collection of sets of size ''n'' such that ''C'' does not have Property B is denoted by ''m''(''n''). The property gets its name from mathematician Felix Bernstein, who first introduced the property in 1908. == Values of ''m''(''n'') == It is known that ''m''(1) = 1, ''m''(2) = 3, and ''m''(3) = 7 (as can by seen by the following examples); the value of ''m''(4) is not known, although an upper bound of 23 (Seymour, Toft) and a lower bound of 21 (Manning) have been proven. At the time of this writing (August 2004), there is no OEIS entry for the sequence ''m''(''n'') yet, due to the lack of terms known. ; ''m''(1) : For ''n'' = 1, set ''X'' = , and ''C'' = ; ''m''(2) : For ''n'' = 2, set ''X'' = and ''C'' = . Then C does not have Property B, so ''m''(2) <= 3. However, ''C'' ; ''m''(3) : For ''n'' = 3, set ''X'' = , and ''C'' = (the Steiner triple system ''S''7); ''C'' does not have Property B (so ''m''(3) <= 7), but if any element of ''C'' is omitted, then that element can be taken as ''Y'', and the set of remaining elements ''C'' ; ''m''(4) : Seymour (1974) constructed a hypergraph on 11 vertices with 23 edges without Property B, which shows that ''m''(4) <= 23. Manning (1995) proved that ''m''(4) >= 20. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Property B」の詳細全文を読む スポンサード リンク
|